package com.cuz.hot100;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Q46fullArray1 {
    public static void main(String[] args) {
        int[] ints = {1, 2, 3, 4};
        System.out.println(permute1(ints));
    }
    public static List<List<Integer>> permute1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Collections.emptyList();
        }
        List<List<Integer>> res = new ArrayList<>();
        //选择第一个节点
        for (int firstChoose = 0; firstChoose < nums.length; firstChoose++) {
            //数是否被使用
            boolean[] hasUse = new boolean[nums.length];
            //当前第一个数以及被使用了
            hasUse[firstChoose] = true;
            //以firstChoose为根节点的树的回溯结果
            LinkedList<Integer> tempRes = new LinkedList<>();
            //选择了第一个数
            tempRes.addLast(nums[firstChoose]);
            //回溯
            process(nums, res, tempRes, 1, hasUse);
        }
        return res;
    }

    /**
     * @param res      总结果集
     * @param tempRes  单分支结果
     * @param numCount 结果中数的数量
     * @param hasUse   那些数被用过
     */
    private static void process(int[] nums, List<List<Integer>> res, LinkedList<Integer> tempRes, int numCount, boolean[] hasUse) {
        //数都用过了
        if (numCount == nums.length) {
            res.add(new ArrayList<>(tempRes));
            return;
        }
        //选择下一个数
        for (int i = 0; i < nums.length; i++) {
            //如果数使用过了 那么下一个
            if (hasUse[i]) {
                continue;
            }
            //使用这个数
            hasUse[i] = true;
            tempRes.addLast(nums[i]);
            numCount++;
            //继续下一个数
            process(nums, res, tempRes, numCount, hasUse);
            //放弃使用这个数
            hasUse[i] = false;
            tempRes.removeLast();
            numCount--;
        }
    }

}
